1. Field of the Invention
This invention relates to random number generators and in particular to random number generators based on detection of quantum phenomena.
2. Description of the Related Art
A random number generator is a device which produces a stream of random numbers or numbers that are nearly random, and not always the same number. A number in this stream is said to be fully random if it has no “memory” of what has gone before it. Statistically speaking, its conditional probability distribution given the past, being independent of its past, equals its unconditional probability distribution. Moreover, it is usually desirable that, for each integer n≧1, the so-called marginal distribution of the nth number in the stream have the same distribution as the first one. The numbers are then said to be stationary (or have identical distributions). For simplicity, all sequences of truly random numbers are generally to be interpreted as being fully random and stationary, and as possibly having equally likely occurrences of each number being produced, as the context might hopefully indicate. It has proved to be very difficult to produce truly random numbers. While people may be capable of producing somewhat random numbers by picking numbers out one at a time, they certainly cannot do so fast enough to meet the requirements of modern usage. Therefore, for all practical purposes, machines are used to produce random numbers.
Most machines and methods heretofore employed for producing random numbers are either “deterministic”—they follow a fixed, totally predictable recipe—or else are still far from truly random. Some devices produce nearly truly random numbers, but they are subject to being skewed by external influences or are very delicate and expensive to maintain. For many purposes an approximation of randomness has turned out to be acceptable. For an increasing number of other purposes, something closely approximating true randomness is a necessity.
Random numbers are most commonly thought of as having security applications such as for sending encrypted messages. Random numbers are useful for security purposes because they create inherently unpredictable sequences which cannot be easily duplicated, studiously replicated or discovered by accident. For many lower security applications, a random number generator with a reasonable degree of randomness will suffice. Higher security applications demand a greater degree of true randomness.
Another problem that exists with current random number generators, apart from the “level of randomness” of the numbers that they are able to produce, is that sufficient numbers of random numbers cannot be produced quickly enough for contemporary applications. This is significant in security applications where messages are encoded with a string of random numbers by adding a bit in the string to each bit in the message. The result appears to be nonsense to any recipient until it is decoded by subtracting out the string to recover the message. Ideally, the random number string should be as long as the message itself. In practice, a string—known as a “key”—is used repeatedly and it is hoped the string cannot be discovered. The length of the key is critically important because each additional random bit in the string doubles the security level of the cipher. Naturally, if production of sufficient numbers of random numbers were possible and practical, the level of security enjoyed for encrypted messages would increase exponentially.
In addition to security applications, random numbers are increasingly essential for scientific investigations including studies of physical laws, investigations and constructions of probability distributions, analyses of the performance of mathematical algorithms in principle and as applied practically to devices, and notably for development of artificial intelligence. Random number generators are used in the assessment of the performance of machines to help construct a large variety of representative situations. The sampling thus obtained provides feedback which is used to learn more about the process or operation being studied. As with security applications, problems exist regarding the availability of a sufficient volume of random numbers and with the true randomness of the numbers produced. In a growing number of areas of scientific inquiry, the ability to produce large numbers of random numbers can be critical. Certain research, such as large-scale Monte Carlo simulations, requires millions of random numbers to yield useful information. In sensitive analyses where essentially true randomness in a sampling is necessary to obtain sound results, any significant lack of randomness can unacceptably skew test data and frustrate the research.
In part due to the need for large numbers of random numbers, the technique of producing “pseudo-random” numbers evolved. Pseudo-random numbers are generated using an arithmetical algorithm having an output of numbers which can pass many statistical tests of randomness. Another important aspect of arithmetically produced random numbers is that they can be replicated. This is useful for purposes of testing and analyses, but potentially disastrous for security applications. While pseudo-random numbers are statistically random for most applications, and have the application specific advantage of being reproducible, they suffer from one major flaw—they repeat. For example, a popular pseudo-random number generator is the linear-congruential generator. The linear-congruential generator of degree k produces non-negative integers less than some given integer m, where m≧2. At some point, if the generator is asked to produce mk+k integers, its last k integers must have already occurred previously. Since each integer produced by the generator is based on the same algorithm, and is therefore dependent on the previous k integers, this leads into a cycle of repetition that the generator cannot escape. In this sense, each pseudo-random number generator has a finite period. The best linear-congruential generators have a period exceeding 2 billion. Shift-register algorithms have been used to greatly extend the period of the generator. Even so, the fact remains that, regardless of the length of the period of a pseudo-random number generator, the numbers which are the product of the technique are ultimately deterministic and certainly not truly random.
Most machines are understood to function in the realm of classical mechanics according to the physical laws stated by Newton. The Newtonian world (including the essentially mechanistic world of Maxwell's equations concerning the behavior of electricity and magnetism) has at its core, the feature and key premise that if all the initial conditions (positions, velocities, charges, etc.) of the components of an isolated physical system are known, all of its future behavior can be known and predicted. It is therefore ultimately deterministic, the generation of truly random numbers or random behavior therefrom being inherently impossible.
Moving closer to the observation of quantum phenomena, many devices have been constructed that take sample measurements of a physical process (sometimes a macro-scopic, but sometimes a micro-scopic process). The measurements are converted into a sequence of elements, each element hopefully having little or no memory (but whether these elements actually lack memory of any of their predecessors depends both on the measuring apparatus and the physical process). Production of random numbers from a physical process creates a string of numbers which, even if not purely random, may seem to be highly so and is largely unrepeatable. This lack of repeatability is a liability in scientific applications, but can be circumvented by recording and/or storing the actual numbers generated if it is not too costly. Conversely, lack of repeatability itself is not necessarily a disadvantage and may well be an asset in security applications and the investigation of artificial intelligence.
Ostensibly random numbers can be generated using “noise” created by minor fluctuations in electronic circuits. It is disputed whether such electronic noise devices generate true random numbers. Unfortunately, they are often innately slower than pseudo-random number generators making them unsuitable for any application where a substantial quantity of random numbers is required. Another drawback to noise based random number generators is that their delicate construction requires constant, minute checking to verify that the device has not skewed away from producing true randomness. Electronic noise devices can become unstable over time. Noise levels are typically affected by fluctuations in temperature and line voltage. Lastly, such devices are very sensitive to surrounding electro-magnetic fields so that any fluctuation in nearby electromagnetic fields can change the output of the device in a deterministic way, thereby skewing the noise away from randomness.
Because radioactive decay is thought to be a memoryless quantum process, independent from atom to atom, random numbers have been produced by monitoring the successive decay times of a chunk of radioactive material. Devices which do so are believed to produce essentially truly random results as opposed to electronic noise devices. However, radioactive materials must be shielded and may therefore be inappropriate for many locations, such as personal computers. As with noise based devices, radioactive decay devices produce random numbers at unacceptably slow rates.
Recently there have been advances in the production of random numbers using spatially stochastic processes. Using a two-dimensional position-sensitive photon-counting detector, the locations of detected photoevents on a two-dimensional detector are tracked. A random sequence of numbers is produced based upon the location (not the time) of photoelectrons emitted from a photocathode. While promising, random number generation based on photoevent locations suffers from a number of vexing problems. The photoevent random number generator is large in size, making it impractical for many applications. It is also complicated to set up and is dependent on position, resolution, speed and dead time.
Other advances in related fields have focused on the polarized nature of light. Photons have many different polarizations. If a photon is passed at normal incidence through a birefringent crystal, such as calcite, the photon will pass straight through the crystal, with its polarization unchanged if it is polarized perpendicular to what is referred to herein as the optic axis of the crystal. If the photon entering the crystal is already polarized along the optic axis, it will emerge with its polarization unchanged but be shifted to a different path than the photons with perpendicular polarization. The photons that have emerged from the crystal can be detected using detectors, such as photomultiplier tubes, established in the two respective paths. If a photon enters the crystal with an axis of polarization, say, half-way between the two rectilinear polarization directions, it will be repolarized into either rectilinear polarization direction and follow its corresponding path with equal probability. These repolarized photons are believed to lose all memory of their original diagonal polarization. Relying on the use of two detectors, the diagonally polarized photons have been utilized by quantum cryptographers to advance a clever scheme for secure exchange of a secret random key that can subsequently be used to send secret messages. An essential part of the scheme is to thwart eavesdroppers to the message, using the random repolarization of incident photons having polarizations diagonal to the optic axis of the crystal. Any measurements by the eavesdropper of such photons would repolarize them and erase the message content inherent in their original polarizations.